In computer networks, network adapters are used to connect host computer systems to external computer networks. A network adapter is typically coupled with the host computer system through a shared data transfer resource, such as a peripheral bus or system bus. Also normally accessible through the shared bus is a host memory, in which data structures that are shared between the adapter and the host computer system are stored. The host memory typically contains data in the form of cells or packets that are to be transferred to the network adapter and subsequently transmitted onto the computer network. Further, the host memory is used to store cells and packets written by the network adapter after the cells and packets are received from the computer network.
The shared bus that is used to couple the network adapter with the host computer system is shared among multiple competing processes within the network adapter. These processes must be granted access to the shared bus in a manner that is fair and which guarantees minimal service levels negotiated for virtual circuits created by the host computer system through the network adapter. Access to the bus by requesters within the network adapter is effectuated by granting access to a set of logic that operates the bus for the network adapter, such as a Direct Memory Access (DMA) logic.
For example, in computer networking technologies such as Asynchronous Transfer Mode (ATM), virtual circuits are established having several negotiated performance parameters. These performance parameters are known as Quality of Service (QoS) parameters. Quality of Service parameters include average throughput, peak throughput, and latency tolerance. In order that the level of performance guaranteed by the QoS parameters not be compromised, access to any shared resources must be allocated among multiple requesters associated with multiple virtual circuits in accordance with the negotiated quality of service parameters for each virtual circuit. This problem is exacerbated by the large number of virtual circuits permitted in computer network technologies such as ATM.
In an alternative example of modern networking technology, there is also the concept of "flows" for a negotiated service level. In such systems, the service level may be defined on a packet by packet basis, without necessarily setting up virtual circuits, and without creating cells from packets. In this type of system, access to the shared resource must be allocated such that the negotiated service level is similarly maintained, albeit on a packet by packet basis.
A further problem exists in communication of status information from the network adapter to the host computer system. Such information is often passed through the same shared bus resource over which packet or cell data is passed. If this information is not communicated in a timely manner between the network adapter and the host computer system, any efficiencies in moving data between the host and the network adapter will be negated. It is therefore further required that the shared bus be used to communicate status information in a manner that does not adversely effect the transmit or receive performance of the network adapter.
In existing systems, there are a relatively small number of requesters. For example, in a system having only one transmit queue and one receive queue in the host, there can be only a proportionally small number of competing requests for any shared data transfer resource, since the processing within each of the two queues is typically sequential. However, when a large number of independent transmit and receive queues are used, many concurrent requests for access to the shared data transfer resource may be simultaneously present. These multiple concurrent requests must be processed correctly, and with consideration of the relative priority or negotiated service level of each request.
The contents of transmit and receive queues in host memory are generally some number of descriptors, each descriptor identifying an area of host memory in which data is or may be stored. In existing systems, the networking adapter has obtained decriptors and data from the host in a strictly sequential fashion. For example on transmit, the adapter first reads one or more descriptors, followed by the data indicated by those descriptors. When multiple independent queues are used, it is desirable to interleave different types of requests from different data flows, such as requests to move descriptors from a first host queue and requests to move data indicated by descriptors already fetched from a second host queue.
Also in systems using multiple transmit queues within the host computer system, it is impracticable to use a large FIFO in the adapter to store data for each transmit queue. Therefore a system of arbitrating for requests to move data from the multiple transmit queues into the FIFOs within the adapter must efficiently allocate access to any shared data transfer resource. Otherwise a FIFO may be underrun, potentially resulting in the QoS parameters for a connection being violated. This problem is particularly difficult because the future availability of the shared resource may be difficult to predict. Each request for the shared data transfer resource must therefore be processed in a way that avoids underrunning any of the FIFOs such that they do not become empty.
In addition to the above design issues there is also a well known problem of maintaining fairness between transmit and receive operations. Thus it is required that neither transmit nor receive data be given excessive priority over the other.
It is therefore desirable to have a new system for arbitrating between multiple requesters for a shared resource such as a peripheral bus. The new system should be tailored to meet the needs of a network adapter for networking technologies such as ATM. Such a new system should also provide support for Quality of Service requirements of a multiple virtual circuit system such as ATM. And further the system should provide service for a large number of potential requesters. An acceptable degree of fairness must be guaranteed between transmit and receive operations. And the new design should be flexible enough so that parameters may be adjusted to control the eventual service provided to different parts of the system in the network adapter so that fairness is perceived by the eventual users of the network.